#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::string expend(const std::string& s){
    std::string res="@#";
    for(int i=0;i<s.size();i++)res+=s[i],res+='#';
    res+='%';
    return res;
}
std::vector<int> Manacher(const std::string& s){
    auto t=expend(s);
    std::vector<int>p(t.size());
    for(int i=1,r=0,c=0;i<t.size()-1;i++){
        p[i]=(r>i?std::min(p[2*c-i],r-i):1);
        while(t[i-p[i]]==t[i+p[i]])++p[i];
        if(i+p[i]>r)r=i+p[i],c=i;
    }
    return p;
}
void fc() {
    std::string s;
    std::cin>>s;
    int n=s.size();

    int k=0;
    while(k<n-1-k&&s[k]==s[n-1-k])k++;
    if(k*2>=n){
        std::cout<<s<<"\n";return;
    }

    std::string t=s.substr(k,n-2*k);
    int m=t.size();
    auto p=Manacher(t);

    int mx_len=0,idx=0;

    for(int i=1;i<p.size()-1;i++){
        if(p[i]<=1)continue;
        int start=(i-p[i])/2;
        int len=p[i]-1;
        int end=start+len-1;

        if(start==0||end==m-1){
            if(len>mx_len){
                mx_len=len;
                idx=start;
            }
        }
    }

    std::cout<<s.substr(0,k)+t.substr(idx,mx_len)+s.substr(n-k,k)<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin>>t;
    while (t--) fc();
    return 0;
}